class Solution {
public:
    /*
        设dp[i]为包含i位置元素的所有摆动序列中，最长摆动序列的长度
        以i位置元素结尾的摆动序列可以分为两种情况：
            1. 最后呈上升趋势
            2. 最后呈下降趋势
        因此，我们可以创建两个表：
            1. f[i]表示以i位置结尾的，呈上升趋势的最长摆动序列长度
            2. g[i]表示以i位置结尾的，呈下降趋势的最长摆动序列长度
        最后结果取f[i]和g[i]最大的值即可
    */
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        int ret = 1;
        vector<int> f(n, 1);
        auto g(f);

        for (int i = 1; i < n; ++i)
        {
            //遍历所有可能的子序列
            for (int j = i - 1; j >= 0; --j)
            {
                //如果呈上升趋势，则找前面呈下降趋势的最长摆动序列长度
                if (nums[i] > nums[j])
                    f[i] = max (f[i], 1 + g[j]);

                //如果呈下降趋势，则找前面呈上升趋势的最长摆动序列长度
                if (nums[i] < nums[j])
                    g[i] = max (g[i], 1 + f[j]);

                ret = max (ret, max(f[i], g[i]));
            }
        }

        return ret;
    }
};